using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;

namespace GeneradorPosiciones
{
    public class Pos_Gen
    {

        public List<Point> Gen_Formation_A(List<Point> Frontera, int unitX = 10, int unitY = 10)
        {
            List<Point> fpoint = new List<Point>();
            Queue<Point> q = new Queue<Point>();

            Random R = new Random();
            Point P;
            do
            {
                P = new Point(R.Next(0, 800), R.Next(0, 600));
            } while (!PointInBoundary(Frontera, P));

 
            q.Enqueue(P);


            while(q.Count>0)
            {
                Point checkPoint = q.Peek();
                Point left = new Point(checkPoint.X - unitX, checkPoint.Y);
                while (PointInBoundary(Frontera,left) && !fpoint.Contains(left))
                {
                    fpoint.Add(left);
                    Point top = new Point(left.X, left.Y + unitY);
                    if (PointInBoundary(Frontera, top) && !fpoint.Contains(top))
                        q.Enqueue(top);
                    Point bottom = new Point(left.X, left.Y - unitY);
                    if (PointInBoundary(Frontera, bottom) && !fpoint.Contains(bottom))
                        q.Enqueue(bottom);
                    left = new Point(checkPoint.X - unitX, checkPoint.Y);
                }
                Point right = new Point(checkPoint.X + unitX, checkPoint.Y);
                while (PointInBoundary(Frontera, right) && !fpoint.Contains(right))
                {
                    fpoint.Add(right);
                    Point top = new Point(right.X, right.Y + unitY);
                    if (PointInBoundary(Frontera, top) && !fpoint.Contains(top))
                        q.Enqueue(top);
                    Point bottom = new Point(right.X, right.Y - unitY);
                    if (PointInBoundary(Frontera, bottom) && !fpoint.Contains(bottom))
                        q.Enqueue(bottom);
                    right = new Point(checkPoint.X - unitX, checkPoint.Y);
                }
                q.Dequeue();
            }
            return fpoint;
        }

        public bool PointInBoundary(List<Point> Poligono, Point p)
        {
           int counter = 0;
           int i;
           int xinters;
           Point p1;
           Point p2;
           int n = Poligono.Count;

           p1 = Poligono[0];
           for (i = 1; i <= n; i++)
           {
               p2 = Poligono[i % n];
              if (p.Y > Math.Min(p1.Y, p2.Y))
              {
                 if (p.Y <= Math.Max(p1.Y, p2.Y))
                 {
                    if (p.X <= Math.Max(p1.X, p2.X))
                    {
                       if (p1.Y != p2.Y) {
                          xinters = (p.Y - p1.Y) * (p2.X - p1.X) / (p2.Y - p1.Y) + p1.X;
                          if (p1.X == p2.X || p.X <= xinters)
                             counter++;
                       }
                    }
                 }
              }
              p1 = p2;
           }
           if (counter % 2 == 0)
           {
              return(false);
           }
           else
           {
              return(true);
           }
        }

    }
}
